package week02

// 23. 合并K个升序链表
// https://leetcode-cn.com/problems/merge-k-sorted-lists/

// 二叉堆

func mergeKLists(lists []*ListNode) *ListNode {
	var proc = &ListNode{}
	var head = proc

	heap := &BinaryHeap{}
	for _, list := range lists {
		if list != nil {
			heap.Push(list)
		}
	}

	for !heap.Empty() {
		node := heap.Pop()
		head.Next = node
		head = head.Next
		if node.Next != nil {
			heap.Push(node.Next)
		}
	}
	return proc.Next
}

// 二叉堆节点
type Node struct {
	key int
	val *ListNode
}

// 二叉堆
type BinaryHeap struct {
	list []*Node
}

func (heap *BinaryHeap) Push(node *ListNode) {
	heap.list = append(heap.list, &Node{
		key: node.Val,
		val: node,
	})
	var cur = len(heap.list) - 1
	var parent = (cur - 1) / 2
	// 调整二叉堆
	for parent >= 0 {
		if heap.list[parent].key > heap.list[cur].key {
			heap.list[parent], heap.list[cur] = heap.list[cur], heap.list[parent]
			cur = parent
			parent = (cur - 1) / 2
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) Pop() *ListNode {
	node := heap.list[0]
	heap.list[0] = heap.list[len(heap.list)-1]
	heap.list = heap.list[:len(heap.list)-1]
	// 调整二叉堆
	var cur = 0
	var child = cur * 2 + 1
	for child < len(heap.list) {
		var other = cur * 2 + 2
		if other < len(heap.list) && heap.list[other].key < heap.list[child].key {
			child = other
		}
		if heap.list[cur].key > heap.list[child].key {
			heap.list[cur], heap.list[child] = heap.list[child], heap.list[cur]
			cur = child
			child = cur * 2 + 1
		} else {
			break
		}
	}
	return node.val
}

func (heap *BinaryHeap) Empty() bool {
	return len(heap.list) == 0
}

type ListNode struct {
	Val int
	Next *ListNode
}